package com.leetcode.partition4;

/**
 * @author `RKC`
 * @date 2021/12/5 9:33
 */
public class LC372超级次方 {

    private static final int MOD = 1337;

    public static int superPow(int a, int[] b) {
        //a⋅b mod n = [(a mod n) (b mod n) ] mod n
        //https://leetcode-cn.com/problems/super-pow/solution/372-chao-ji-ci-fang-jie-ti-bi-ji-by-shol-ikfk/
        int answer = 1;
        for (int i = b.length - 1; i >= 0; i--) {
            answer = (answer * pow(a, b[i])) % MOD;
            a = pow(a, 10);
        }
        return answer;
    }

    public static void main(String[] args) {
        int a = 2;
        int[] b = {1, 0};
        System.out.println(superPow(a, b));
    }

    private static int pow(int a, int n) {
        int res = 1;
        if (a > MOD) a = a % MOD;
        while (n > 0) {
            if ((n & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            n >>= 1;
        }
        return res;
    }
}
